HighLife (automate cellulaire)
Pour les articles homonymes, voir High Life.
Ne doit pas être confondu avec Hashlife.
HighLife est un automate cellulaire similaire au jeu de la vie. Il fut inventé en 1994 par Nathan Thompson.
Propriétés[modifier | modifier le code]
HighLife est un automate cellulaire bidimensionnel dont les cellules peuvent prendre deux états (« vivantes » ou « mortes »). Une cellule morte y naît à l'étape suivante si elle est entourée de 3 ou 6 voisines vivantes, une cellule vivante survit à l'étape suivante si elle est entourée de deux ou trois cellules vivantes.
Ces règles sont très proches de celles du jeu de la vie (seule la condition de naissance pour 6 cellules vivantes voisines diffère). Ainsi, beaucoup de motifs élémentaires de cet automate cellulaire fonctionnent à l'identique dans HighLife. Ce n'est cependant pas le cas des plus complexes[1].
Réplicateur[modifier | modifier le code]
L'intérêt d'HighLife vient de l'existence d'un motif appelé le « réplicateur ». Au bout de douze itérations, un réplicateur donne naissance à deux réplicateurs, décalés l'un de l'autre de plusieurs cellules. Ces réplicateurs vont à leur tour se reproduire, selon une ligne diagonale[1].
HighLife possède donc une structure capable de se reproduire à l'identique, comme le constructeur universel de John von Neumann. Dans le jeu de la vie, une telle figure a été trouvée en 2010, baptisée gemini à cause de sa forme, deux machines identiques reliées par une énorme ligne de planeurs[2]. C'est cependant une figure extrêmement complexe en comparaison du réplicateur de HighLife.
Références[modifier | modifier le code]
- David Eppstein, « Growth and Decay in Life-Like Cellular Automata », dans Game of Life Cellular Automata, Springer London, , 71–97 p. (ISBN 978-1-84996-216-2, lire en ligne)
- (en-US) #author.fullName}, « First replicating creature spawned in life simulator », sur New Scientist (consulté le )
